import java.util.Deque;
import java.util.LinkedList;

public class Leetcode {
}

//leetcode:151:反转字符串中的单词
//方法一：编写函数
class Solution1 {
    public String reverseWords(String s) {
        s = s.trim();
        StringBuilder sb = trimword(s);

        reverse(sb,0,sb.length()-1);
        reverseWord(sb);
        return sb.toString();
    }

    public void reverse(StringBuilder sb,int left,int right){
        while(left < right){
            char ch = sb.charAt(left);
            sb.setCharAt(left++,sb.charAt(right));
            sb.setCharAt(right--,ch);
        }
    }

    public StringBuilder trimword(String s){
        int left = 0;
        int right = s.length()-1;
        StringBuilder sb = new StringBuilder();
        while(left <= right){
            char ch = s.charAt(left);
            if(ch != ' '){
                sb.append(ch);
            }else if(sb.charAt(sb.length()-1) != ' '){
                sb.append(ch);
            }
            left++;
        }
        return sb;
    }

    public void reverseWord(StringBuilder sb){
        int left = 0;
        int right = 0;
        int n = sb.length();
        while(left < n){
            while(right < n && sb.charAt(right) != ' '){
                right++;
            }

            reverse(sb,left,right-1);
            left = right+1;
            right++;
        }
    }
}

//方法二：双端队列
class Solution2 {
    public String reverseWords(String s) {
        int left = 0;
        int right = s.length()-1;
        while(left <= right && s.charAt(left) == ' '){
            left++;
        }
        while(left <= right && s.charAt(right) == ' '){
            right--;
        }

        Deque<String> deque = new LinkedList<>();
        StringBuilder word = new StringBuilder();

        while(left <= right){
            char ch = s.charAt(left);
            if((word.length() != 0) && (ch == ' ')){
                deque.offerFirst(word.toString());
                deque.offerFirst(" ");
                word.setLength(0);
            }else if(ch != ' '){
                word.append(ch);
            }
            left++;
        }
        deque.offerFirst(word.toString());
        StringBuilder sb = new StringBuilder();
        while(!deque.isEmpty()){
            sb.append(deque.poll());
        }
        return sb.toString();
    }
}